package sorted;

import java.util.Arrays;

public class S05_MergeSort {

    public static void main(String[] args) {
        int[] arr = {5,7,2,3,4,1,6,18,9,10,16,56,34,23,11,12,31,17,15};
        int[] sorted = mergeSort(arr);

        System.out.println("排序后的数组为："+ Arrays.toString(sorted));
    }

    public static int[] mergeSort(int[] arr) {
        int length = arr.length;

        if (length < 2){
            return arr;
        }

        int mid = length / 2;
        int[] range1 = Arrays.copyOfRange(arr, 0, mid);
        int[] range2 = Arrays.copyOfRange(arr, mid, length);

        return merge(mergeSort(range1),mergeSort(range2));
    }

    public static int[] merge(int[] arr1,int[] arr2){
        int length1 = arr1.length;
        int length2 = arr2.length;
        int[] result = new int[length1 + arr2.length];

        int i = 0,j = 0;
        while (i<length1 && j<length2){
            if (arr1[i] < arr2[j]){
                result[i+j] = arr1[i];
                i++;
            }else {
                result[i+j] = arr2[j];
                j++;
            }
        }

        int count = i+j;
        int length= i<length1 ? length1 : length2;
        int tail = i < length1 ? i : j;
        int[] tailArr = i < length1 ? arr1 : arr2;
        while (tail < length){
            result[count++] = tailArr[tail++];
        }

        return result;
    }
}


